1. Field of the Invention
This invention generally relates to information storage and, more particularly, to a system and method for peer-to-peer distributed information storage.
2. Description of the Related Art
A peer-to-peer (P2P) computer network uses the diverse connectivity and cumulative bandwidth of network participants, rather than the centralized resources of a relatively low number of servers. Sharing files containing audio, video, data or anything in digital format is very common, and realtime data, such as telephony traffic, is also passed using P2P technology.
A pure P2P network does not have the notion of clients or servers, but only equal peer nodes that simultaneously function as both “clients” and “servers” to the other nodes on the network. This model of network arrangement differs from the client-server model where communication is usually to and from a central server. A typical example of a file transfer that is not P2P, is an FTP server where the client and server programs are quite distinct. The clients initiate the download/uploads, and the servers react to and satisfy these requests.
In “pure” P2P networks the peers act as equals, merging the roles of clients and server. There is no central server managing the network or central router. A hybrid P2P system may have a central server that keeps information on peers and responds to requests for that information. The peers are responsible for hosting available resources (as the central server does not have them), for letting the central server know what resources they want to share, and for making its shareable resources available to peers that request it. Route terminals can be used as addresses, which are referenced by a set of indices to obtain an absolute address. Napster was an example of a centralized P2P network, while KaZaA was more decentralized.
The advantage of a P2P networks is that all clients provide resources, including bandwidth, storage space, and computing power. Thus, as nodes arrive and demand on the system increases, the total capacity of the system also increases. This is not true of a client-server architecture with a fixed set of servers, in which adding more clients could mean slower data transfer for all users. The distributed nature of P2P networks also increases robustness in case of failures by replicating data over multiple peers, and in pure P2P systems, by enabling peers to find the data without relying on a centralized index server. In the latter case, there is no single point of failure in the system.
The P2P overlay network consists of all the participating peers as network nodes. There are links between any two nodes that know each other: i.e. if a participating peer knows the location of another peer in the P2P network, then there is a directed edge from the former node to the latter in the overlay network. Based on how the nodes in the overlay network are linked to each other, P2P networks may be classified as unstructured or structured.
An unstructured P2P network is formed when the overlay links are established arbitrarily. Such networks can be easily constructed as a new peer that wants to join the network can copy existing links of another node and then form its own links over time. Structured P2P network employ a globally consistent protocol to ensure that any node can efficiently route a search to some peer that has the desired file. Such a guarantee necessitates a more structured pattern of overlay links. By far the most common type of structured P2P network is the distributed hash table (DHT), in which a variant of consistent hashing is used to assign ownership of each file to a particular peer, in a way analogous to a traditional hash table's assignment of each key to a particular array slot. Some well known DHTs are Chord, Pastry, Tapestry, CAN, and Tulip.
Using the Chord lookup protocol, node keys are arranged in a circle. The circle cannot have more than 2m nodes. The ring can have ids/keys ranging from 0 to 2m−1. IDs and keys are assigned an m-bit identifier using what is known as consistent hashing. The SHA-1 algorithm is the base hashing function for consistent hashing. The consistent bashing is integral to the probability of the robustness and performance because both keys and IDs (IP addresses) are uniformly distributed and in the same identifier space. Consistent hashing is also necessary to let nodes join and leave the network without disrupting the network.
Each node has a successor and a predecessor. The successor to a node or key is the next clockwise node in the identifier circle. The predecessor of a node or key is the next counter-clockwise node in the id circle. If there is a node for each possible ID, the successor of node 2 is node 3, and the predecessor of node 1 is node 0. However, normally there are holes in the sequence, so, for example, the successor of node 153 may be node 167 (and nodes from 154 to 166 will not exist). In this case, the predecessor of node 167 will be node 153. Since the successor (or predecessor) node may disappear from the network (because of failure or departure), each node records a whole segment of the circle adjacent to it, i.e. the K nodes preceding it and the K nodes following it. One successor and predecessor are kept in a list to maintain a high probability that the successor and predecessor pointers actually point to the correct nodes after possible failure or departure of the initial successor or predecessor.
BitTorrent is a peer-to-peer file sharing protocol used to distribute large amounts of data. The initial distributor of the complete file or collection acts as the first seed. Each peer who downloads the data also upload's them to other peers. Relative to standard Internet hosting, this method provides a significant reduction in the original distributor's hardware and bandwidth resource costs. It also provides redundancy against system problems and reduces dependence on the original distributor.
To share a file or group of files, a peer first creates a small file called a “torrent” (e.g. MyFile.torrent). This file contains metadata about the files to be shared and about the tracker, the computer that coordinates the file distribution. Peers that want to download the file first obtain a torrent file for it, and connect to the specified tracker, which tells them from which other peers to download the pieces of the file. Though both ultimately transfer files over a network, a BitTorrent download differs from a classic full-file HTTP request in several fundamental ways.
The peer distributing a data file treats the file as a number of identically-sized pieces, typically between 64 kB and 4 MB each. The peer creates a checksum for each piece, using the SHA1 hashing algorithm, and records it in the torrent file. Pieces with sizes greater than 512 kB will reduce the size of a torrent file for a very large payload, but is claimed to reduce the efficiency of the protocol. When another peer later receives a particular piece, the checksum of the piece is compared to the recorded checksum to test that the piece is error-free. Peers that provide a complete file are called seeders, and the peer providing the initial copy is called the initial seeder.
Users browse the web to find a torrent of interest, download it, and open it with a BitTorrent client. The client connects to the tracker(s) specified in the torrent file, from which it receives a list of peers currently transferring pieces of the file(s) specified in the torrent. The client connects to those peers to obtain the various pieces. Such a group of peers connected to each other to share a torrent is called a swarm. If the swarm contains only the initial seeder, the client connects directly to it and begins to request pieces. As peers enter the swarm, they begin to trade pieces with one another, instead of downloading directly from the seeder. BitTorrent does not offer its users anonymity. It is possible to obtain the IP addresses of all current, and possibly previous, participants in a swarm from the tracker. This may expose users with insecure systems to attacks.
All of the above-mentioned systems are generally concerned with the retrieval and sharing of complete files, rather than the distribution of segments from a single file across many peers. Conventional information storage backup systems, such as Network Attached Storage (NAS) use a software client (e.g., a PC) that moves information to a RAID-based network storage system. The backup storage location is a large data center which contains enough storage to store information for all the connected users. The data center may be connected via the Internet, for example.
FIGS. 1A and 1B are diagrams depicting a RAID 5 system (prior art). RAID 5 and RAID 6 are well known as systems for the redundant array of independent disks. RAID systems are an example of what is referred to herein as an erasure code. Instead of distributing data “vertically” (from lowest sector to highest) on single disks, RAID 5 distributes data in two dimensions. First, “horizontally” in a row across n number of disks, then “vertically” as rows are repeated. A row consists of equal “chunks” of data on each disk and is referred to as a “stripe”. Each chunk of data, or each disk's portion of the stripe, is referred to as a stripelet.
For RAID 5, one of the stripelets is designated as a parity stripelet. This stripelet consists of the XOR of all the other stripelets in the stripe. The operation for XOR'ing the data for a parity stripelet is referred to as P-calculation. The purpose of the parity is to provide for a level of redundancy. Since the RAID is now depicting a virtual disk consisting of multiple physical disks, there is a higher probability of one the individual physical disks failing. If one of the stripelets cannot be read due to an individual disk error or failure, the data for that stripelet can be reassembled by XOR'ing all the other stripelets in the stripe.
It would be advantageous if a P2P system existed that permitted a user to distribute information among a group of peers in a manner that ensured the confidentiality of the information and protected against peer failures.